package com.leetcode;

import com.leetcode.common.ListNode;

import static com.leetcode.util.LinkedListUtil.createList;
import static com.leetcode.util.LinkedListUtil.printList;

/**
 * 143. 重排链表
 * 寻找链表中点 + 链表逆序 + 合并链表
 *
 * @author fy
 * @date 2022/4/11 19:33
 */
public class Solution143 {

    public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }

        // 跟归并排序寻找中间节点不一样
        ListNode mid = middleNode(head);

        ListNode head1 = head;
        ListNode head2 = mid.next;
        // 切断链表
        mid.next = null;

        ListNode newHead2 = reverseList(head2);

        ListNode cur = new ListNode();
        while (head1 != null && newHead2 != null) {
            cur.next = head1;
            head1 = head1.next;
            cur = cur.next;

            cur.next = newHead2;
            newHead2 = newHead2.next;
            cur = cur.next;
        }
        cur.next = head1 == null ? newHead2 : head1;
    }

    /**
     * 左右踹合并链表
     *
     * @param l1
     * @param l2
     */
    public void mergeList(ListNode l1, ListNode l2) {
        ListNode l1_tmp;
        ListNode l2_tmp;
        while (l1 != null && l2 != null) {
            l1_tmp = l1.next;
            l2_tmp = l2.next;

            l1.next = l2;
            l1 = l1_tmp;

            l2.next = l1;
            l2 = l2_tmp;
        }
    }

    /**
     * 快慢指針求中间节点
     *
     * @param head
     * @return
     */
    private ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    /**
     * 反转链表
     *
     * @param head
     * @return
     */
    private ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode p = head;
        while (p != null) {
            ListNode next = p.next;
            p.next = pre;

            pre = p;
            p = next;
        }
        return pre;
    }

    public static void main(String[] args) {
        ListNode head = createList(new int[]{1, 2, 3, 4, 5, 6});
        printList(head);
        new Solution143().reorderList(head);
        printList(head);
    }

}
